package org.example.algorithm.dp;

public class NumRollsToTargetSolution {
    private static final int NUM_MOD = (int) 1e9+7;

    public static void main(String[] args) {
        NumRollsToTargetSolution solution = new NumRollsToTargetSolution();
        int n = 2;
        int k = 6;
        int target = 7;
        int res = solution.numRollsToTarget(n, k, target);
        System.out.println(res);
    }

    //优化内存占用
    public int numRollsToTarget(int n, int k, int target) {
        if (target < n || target > n * k) {
            return 0;
        }
        if (target == n || target == n * k) {
            return 1;
        }
        int[] dp = new int[target+1];
        //！！！遍历第一个骰子时初始赋值
        dp[0] = 1;
        for (int i=1;i<=n;i++) {
            for (int j=target;j>=0;j--) {
                //!!!不清0，会多算一个dp[j-1]
                dp[j] = 0;
                for (int p=1;p<=k && p<=j;p++) {
                    dp[j] = (dp[j] + dp[j-p]) % NUM_MOD;
                }
            }
        }
        return dp[target];
    }

    public int numRollsToTarget2(int n, int k, int target) {
        if (target < n || target > n * k) {
            return 0;
        }
        if (target == n || target == n * k) {
            return 1;
        }
        int[][] dp = new int[n+1][target+1];
        dp[0][0] = 1;
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=target;j++) {
                for (int p=1;p<=k && p<=j;p++) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-p]) % NUM_MOD;
                }
            }
        }
        return dp[n][target];
    }
}
